TNotes.leetcode

Appearance

⏰0449. 序列化和反序列化二叉搜索树【中等】

0449. 序列化和反序列化二叉搜索树【中等】 ​

1. 📝 题目描述 ​

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例 1：

txt
输入：root = [2,1,3]
输出：[2,1,3]

示例 2：

txt
输入：root = []
输出：[]

提示：

  • 树中节点数范围是 [0, 10^4]
  • 0 <= Node.val <= 10^4
  • 题目数据 保证 输入的树是一棵二叉搜索树。

2. 🎯 s.1 - 前序遍历 + 上下界递归重建 ​

c
// 序列化：前序遍历
char* serialize(struct TreeNode* root) {
    char* buf = (char*)malloc(100000);
    buf[0] = '\0';
    int len = 0;
    void preorder(struct TreeNode* node) {
        if (!node) return;
        if (len > 0) buf[len++] = ',';
        len += sprintf(buf + len, "%d", node->val);
        preorder(node->left);
        preorder(node->right);
    }
    preorder(root);
    return buf;
}

// 反序列化：根据上下界递归重建
struct TreeNode* deserialize(char* data) {
    if (!data || !*data) return NULL;
    int vals[10000], n = 0;
    char* p = data;
    while (*p) {
        vals[n++] = (int)strtol(p, &p, 10);
        if (*p == ',') p++;
    }
    int idx = 0;
    struct TreeNode* build(int lo, int hi) {
        if (idx >= n || vals[idx] < lo || vals[idx] > hi) return NULL;
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = vals[idx++];
        node->left = build(lo, node->val);
        node->right = build(node->val, hi);
        return node;
    }
    return build(-100001, 100001);
}
js
/**
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  const arr = []
  const preorder = (node) => {
    if (!node) return
    arr.push(node.val)
    preorder(node.left)
    preorder(node.right)
  }
  preorder(root)
  return arr.join(',')
}

/**
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  if (!data) return null
  const vals = data.split(',').map(Number)
  let idx = 0
  const build = (lo, hi) => {
    if (idx >= vals.length || vals[idx] < lo || vals[idx] > hi) return null
    const val = vals[idx++]
    const node = new TreeNode(val)
    node.left = build(lo, val)
    node.right = build(val, hi)
    return node
  }
  return build(-Infinity, Infinity)
}
py
class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        arr = []
        def preorder(node):
            if not node:
                return
            arr.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        preorder(root)
        return ','.join(arr)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None
        vals = list(map(int, data.split(',')))
        self.idx = 0
        def build(lo, hi):
            if self.idx >= len(vals) or vals[self.idx] < lo or vals[self.idx] > hi:
                return None
            val = vals[self.idx]
            self.idx += 1
            node = TreeNode(val)
            node.left = build(lo, val)
            node.right = build(val, hi)
            return node
        return build(float('-inf'), float('inf'))
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

算法思路：

  • 序列化：前序遍历将节点值拼接为字符串
  • 反序列化：利用 BST 性质，通过上下界限定左右子树范围，递归重建